

program dijkstral;
const maxn=6;
type path=record
          length:integer;
          pre:0 .. maxn;
     end;
var adj:array[1 .. maxn,1 .. maxn] of integer;
    dist:array[1 .. maxn] of path;
    n,i,j,k,v0,u,min:integer;

procedure dijkstra;
begin
  for i:=1 to n do
    begin
      dist[i].length:=adj[v0,i];
      if dist[i].length<>32767
        then dist[i].pre:=v0
        else dist[i].pre:=0;
    end;
  adj[v0,v0]:=1;
  repeat
    min:=32767; u:=0;
    for i:=1 to n do
      if (adj[i,i]=0) and (dist[i].length<min)
        then begin
               u:=i; min:=dist[i].length;
             end;
    if u<>0
      then
        begin
          adj[u,u]:=1;
          for i:=1 to n do
            if (adj[i,i]=0) and (dist[i].length>dist[u].length+adj[u,i])
              then
                begin
                  dist[i].length:=dist[u].length+adj[u,i];
                  dist[i].pre:=u;
                end;
        end;
  until u=0;
end;

procedure print(i:integer);     
begin
  if i=v0 then write(v0)
    else begin
           print(dist[i].pre);
           write('---->',i,'(',dist[i].length,')');
         end;
end;


begin 
  assign(input,'input.dat'); reset(input);
  assign(output,'output.dat'); rewrite(output);
  readln(n,v0);
  for i:=1 to n do
    for k:=1 to n do
    begin
      read(j);
      if j<>0 then adj[i,k]:=j else  adj[i,k]:=32767; 
      if i=k  then adj[i,k]:=0;
    end;

  dijkstra;

  print(6);               
  writeln;
  for i:=1 to n do write(dist[i].length,' '); 
  close(input); close(output);
end.